#!/usr/bin/perl -w
#
#NOTES: 
#
# use \savebox to make numbers align??
# use fractions for all computations
# add Nine Chapters problems w/ drop down menu

#
#PERL MODULES
#

use strict;
use CGI qw/:standard/;
#use CGI qw/-no_undef_params -nosticky :all/;
use CGI::Carp qw(fatalsToBrowser);

#
#VARIABLES
#

my $m_num; 
my $M;
my $N;
my $cintegers = 1;
my $cmatrix = "";
my $denominator;
my $error = "";
my $formattedtabledata;
my $inputerror = "";
my $matrix = "";
my $noninteger = 0;
my $pm = "";
my $pm1 = 1;
my $print_a = "";
my $query = new CGI; 
my $reducetens = 1;
my $s; #step
my $step;
my $t=0;
my $table_a = ""; 
my $table_header = ""; 
my $usegcf =0;
my @JZSSproblems = "";
#Matrices
my @a; #a[$s][$i][$j]  ## Main Matrix (foundation) s=stage/step; 
my @a_tex = ""; # a, LaTeX
my @c; # Chinese counting rod matrices
my @xyc; #counting rods, in xymatrix 
my @c_tex = ""; # Chinese counting rod matrices, LaTeX 
my @f_tex = ""; # formulas, LaTeX 
my @m; #matrices from books
my @u; #user input from webpage
#Notes
my @boardnotes = "";
my @calcnotes = "";
my @cresult = "";
my @denom;
my @formula = "";
my @formulanotes = "";
my @frac;
my @num;
my @output;
my @result = "";
my @sign;
my @xymatrix = "";


#
#MATRICES - Database of the problems; hash of hashes?
#

#JZSS
#3
$m[1] = [["2", "1", "0", "1"], ["0", "3", "1", "1"], ["1", "0", "4", "1"]];
#12
$m[2] = [["1", "1", "0", "40"], ["0", "2", "1", "40"], ["1", "0", "3", "40"]];
#13
$m[3] = [["2", "1", "0", "0", "0", "721"], ["0", "3", "1", "0", "0", "721"], ["0", "0", "4", "1", "0", "721"], ["0", "0", "0", "5", "1", "721"], ["1", "0", "0", "0", "6", "721"]];
#15
$m[4] = [["2", "-1", "0", "1"], ["0", "3", "-1", "1"], ["-1", "0", "4", "1"]];

# YHJZSS
$m[5] = [["2", "1", "0", "2500"], ["0", "3", "1", "2500"], ["1", "0", "4", "2500"]];

#SXZJ
$m[6] = [["15", "1670", "0", "0", "106000"], ["0", "800", "264", "0", "106000"], ["0", "0", "40", "200", "106000"], ["52", "0", "0", "175/3", "106000"]];

#744.4
$m[7] = [["2", "1", "0", "1"], ["0", "3", "1", "1"], ["1", "0", "4", "2"]];

#747.3
$m[8] = [["4", "-1", "0", "300"], ["0", "5", "-1", "300"], ["-1", "0", "6", "300"]];

#750.2
$m[9] = [["2", "4", "0", "0", "40"], ["0", "2", "7", "0", "40"], ["0", "0", "4", "7", "30"], ["1", "0", "0", "8", "24"]];

#SFTZ
#4**
$m[10] = [["1", "1", "0", "42"], ["0", "2", "1", "42"], ["1", "0", "3", "42"]];
#5**
$m[11] = [["2", "3", "0", "2040"], ["0", "5", "6", "640"], ["3", "0", "7", "2980"]];
#8**
$m[12] = [["2", "4", "0", "0", "40"], ["0", "2", "7", "0", "40"], ["0", "0", "4", "7", "30"], ["1", "0", "0", "8", "24"]];

#359.3
$m[13] = [["10", "1", "0", "0", "1"], ["0", "10", "2", "0", "1"], ["0", "0", "10", "3", "1"], ["4", "0", "0", "10", "1"]];

#366.4
$m[14] = [["1", "1", "0", "42"], ["0", "2", "1", "42"], ["1", "0", "3", "42"]];

#372.3
$m[15] = [["2", "4", "0", "0", "40"], ["0", "2", "7", "0", "40"], ["0", "0", "4", "7", "30"], ["1", "0", "0", "8", "24"]];

#373.3
$m[16] = [["1", "8", "0", "0", "24"], ["0", "7", "4", "0", "30"], ["0", "0", "7", "2", "40"], ["2", "0", "0", "4", "40"]];

#374.1
$m[17] = [["2", "7", "0", "0", "40"], ["0", "4", "7", "0", "30"], ["0", "0", "8", "1", "24"], ["4", "0", "0", "2", "40"]];

$m[18] = [["1", "1/3", "0", "0", "0", "1442"], ["0", "1", "1/4", "0", "0", "1442"], ["0", "0", "1", "1/5", "0", "1442"], ["0", "0", "0", "1", "1/6", "1442"], ["1/2", "0", "0", "0", "1", "1442"]];

$m[19] = [["1", "-1/3", "0", "0", "0", "719"], ["0", "1", "-1/4", "0", "0", "719"], ["0", "0", "1", "-1/5", "0", "719"], ["0", "0", "0", "1", "-1/6", "719"], ["-1/2", "0", "0", "0", "1", "719"]];

$m[20] = [["1", "-1/3", "0", "0", "0", "0"], ["0", "1", "-1/4", "0", "0", "0"], ["0", "0", "1", "-1/5", "0", "0"], ["0", "0", "0", "1", "-1/6", "0"], ["1/2", "0", "0", "0", "1", "721"]];

$m[21] = [["10", "1", "0", "0", "9976"], ["0", "10", "2", "0", "9976"], ["0", "0", "10", "3", "9976"], ["4", "0", "0", "10", "9976"]];

$m[22] = [["2/5", "1", "0", "6780"], ["0", "2/3", "1", "6780"], ["1", "0", "2/7", "6780"]];

$m[23] = [["3", "30", "0", "0", "0", "0", "0", "0", "0", "45"], ["0", "30", "-120", "0", "0", "0", "0", "0", "0", "0"], ["0", "0", "100", "-50", "0", "0", "0", "0", "0", "0"], ["0", "0", "0", "30", "30", "0", "0", "0", "0", "18"], ["0", "0", "0", "0", "50", "10", "0", "0", "0", "45"], ["0", "0", "0", "0", "0", "15", "17", "0", "0", "111/2"], ["0", "0", "0", "0", "0", "0", "20", "-40", "0", "28"], ["0", "0", "0", "0", "0", "0", "0", "20", "-10", "0"], ["2", "0", "0", "0", "0", "0", "0", "0", "80", "34"]];

@JZSSproblems = (1..23);


#
# INITIALIZATION
#
#$s=0 unless $s = $query->param('s');

#
#  SUBROUTINES
#

#LOAD MATRIX SUBROUTINES

# comment has the better name
# Stage 0:
# info from database or from CGI module
# convert it into a matrix that we can operate on
# must be all integers
# converts fractions into integers by finding greatest common factor
sub elimfracs { #subConvertFractionsToIntegers
	my ($s) = @_;
	foreach my $n (1..$N){
		foreach my $m (1..$M){
			if ($a[$n][$m][$s] =~m/(\d+)\/(\d+)/){
				my $num = $1;
				my $denom = $2;
				my $gcf = &gcf($num,$denom);
				$num /= $gcf;
				$denom /= $gcf;
				foreach my $p (1..$M) {
					$a[$n][$p][$s] *= $denom;
				}
			}
		}
	}
	return @a;
}

# puts matrix @m into matrix @a
# iterates through all rows and columns to copy matrixM into matrixA
# trying to put matrix M into matrix a[0] (step 0)
# initializes A, step 0
sub m2a { #not quite sure anymore what this does
 	my ($t) = @_;
	$N = $#{$m[$t][0]}; 
	$M = $N + 1;
	foreach my $n (1..$N) {
		foreach my $m (1..$M) {
			$u[$n][$m] = $m[$t][$n-1][$m-1];	# possibly converting from arrays to hashes
												# @u is user inputted matrix
			if ($m[$t][$n-1][$m-1] =~s/^-//){ 	# matching strings to find if plus or minus number
				$sign[$n][$m] = -1;  			# problem converting strings into integers?
			}else{
				$sign[$n][$m] = 1;  
			}
			if (($m[$t][$n-1][$m-1] == "") or ($m[$t][$n-1][$m-1] =~ m/^0+$/)) { #blank or all zeros, possibly -
				$num[$n][$m] = 0;
				$denom[$n][$m] = 1;
				$sign[$n][$m] = 1;
			}elsif ($m[$t][$n-1][$m-1] =~ m/^(\d+)$/) {
				$num[$n][$m] = $1;
				$denom[$n][$m] = 1;
			}elsif ($m[$t][$n-1][$m-1] =~m/^(\d+)\/(\d+)$/){
				$num[$n][$m] =$1;
				$denom[$n][$m] =$2;
				if ($denom[$n][$m] == 0) {
					$denom[$n][$m] = 1; #print error??
				}
				my $gcf = &gcf($num[$n][$m],$denom[$n][$m]);
				$num[$n][$m] /=$gcf || print "Divided by 0\n";
				$denom[$n][$m] /=$gcf || print "Divided by 0\n";			
			}else{
				print "Error! \"$m[$t][$n-1][$m-1]\" \n";
			}
		}
		# if testing for fraction, setting denominator to 1, needs to be cut
		my $lcm = 1;
		my $gcf = &gcf($denom[$n][1],$denom[$n][2]);
		foreach my $m (3..$M) {
			$gcf = &gcf($gcf,$denom[$n][$m]);
		}
		foreach my $m (1..$M) {
			$lcm *= $denom[$n][$m];
 			$lcm /= $gcf;
		}
		foreach my $m (1..$M) {
			unless ($denom[$n][$m] == 0 ){
				$a[$n][$m][$s] = ($sign[$n][$m] * $num[$n][$m] * $lcm) / $denom[$n][$m];
			}
		}
	}
	return @a;
}

# initializes A step 0 with random
sub random2a { #subAssignRandomEntriesToMatrix
	 my ($s) = @_;
	foreach my $n (1..$N) {
		foreach my $m (1..$N) {
			$a[$n][$m][$s] =  int(rand(8))+1;
		}
	$a[$n][$N+1][$s] =  int(rand(149))+1;
	}
	return @a;
}

# takes old a, iterates to next step, copies to next step
sub nexta {
	my ($s) = @_;
	foreach my $i (1..$N) {
		foreach my $j (1..$M) {
			$a[$i][$j][$s]=$a[$i][$j][$s-1];	# indices appear to be backwards
		}		
	}
	return @a;
}

# MATRIX CALCULATION SUBROUTINES
# vestigial tests for integers, not needed, not right
# no fractions involved, keep test just to avoid problems?
sub noninteger { #subMatrixHasNonIntegerEntry
	 my ($s) = @_;
	$noninteger = 0;
	foreach my $n (1..$N) {
		foreach my $m (1..$M) {
			if ($a[$n][$m][$s] != int($a[$n][$m][$s])) {$noninteger = 1};
		}
	}
	return $noninteger;
}

# for the determinant; some will have alternating signs
# look at LaTeX output; is just creating for LaTeX
sub pm { #subReturnPlusSignIfEvenMinusSignIfOdd
	my ($n) = @_;
	if ($n % 2 == 0) {$pm = "+"} else {$pm = "-"};
	return $pm;
}

# gives the +/- for the actual calculations; cf. pm()
sub pm1 { #subReturnOneIfEvenNegativeOneIfOdd
	my ($n) = @_;
	if ($n % 2 == 0) {$pm1 = 1} else {$pm1 = -1};
	return $pm1;
}


sub determinants {
	#First part of calculation
	my $s=0; #steps for first part
	
	# formats for display, before calculations
	&elimfracs;
	$a_tex[$s] = &a2tex;
	&a2c($s);
	$c_tex[$s] = &c2tex($s);
	$xymatrix[$s] = &xysetneg($s);
	&f2tex($s);
	$boardnotes[$s] .= qq{<p>We arrange the entries on the counting board as follows (note that we remove any fractions by multiplying the entire column by a suitable integer):</p>};
	$calcnotes[$s] .= qq{<p>This corresponds to the following augmented matrix:</p>};
	$formulanotes[$s] .= qq{<p>Using variables, we can show what this corresponds to in terms of an exemplar:</p>};
	
	# now start calculation
	my $anN = $a[$N][1][$s];
	foreach $s (1..$N-2) {
		&nexta($s);
		$anN *= $a[$s][$s+1][$s];
		$a[$N][$s+1][$s] = &pm1($s) * $anN;
		$a_tex[$s] = &a2tex($s);
		&a2c($s);
		$c_tex[$s] = &c2tex($s);
		$xymatrix[$s] = &xysetneg($s);
		&f2tex($s);
		my $x = $s+1;
		my $y = $N-$s+1;
		#<img src="../cgi-bin/mathtex.cgi?\\usepackage{euler}$a[$N][$s][$s]" alt="" border=0 align=middle>
		$boardnotes[$s] .= qq{<p>We multiply the entry located in <i>row $s column 1</i>,  namely <b>$a[$N][$s][$s]</b>, by the entry in <i>row $x column $y</i>, which is <b>$a[$s][$s+1][$s]</b>, change the sign, and place the result, <b>$a[$N][$s+1][$s]</b>, in the entry located in <i>row $x column 1</i>:</p>};
		$calcnotes[$s] .= qq{<p>This corresponds to the following augmented matrix:</p>};
		$formulanotes[$s] .= qq{<p>Using variables, we can show what this corresponds to in terms of an exemplar:</p>};
	};	
	#Second part of calculation
	# move in, 1 by 1, cross-multiply
	$s = $N-1;
	&nexta($s);
	my $t=1; #steps for second part
	$formula[$s] = qq{ k_1 b_{$N} - l_{$N}b_1 };	
	$result[$s] = $a[1][1][$s] * $a[$N][$M][$s] - $a[$N][1][$s] * $a[1][$M][$s] ;
	$a[$N][$M][$s] = $result[$s];
	$cresult[$s] = &num2rods($result[$s]);
	$xymatrix[$s] = &xycrossmult($s);
	my $tempa = $a[1][1][$s-1] * $a[$N][$M][$s-1];
	my $tempb = $a[$N][1][$s-1] * $a[1][$M][$s-1] ;
	$boardnotes[$s] .= qq{<p>We now begin a kind of "cross-multiplication": </p>
	<p>(1) We begin with the entry located in <i>row $M column 1</i>,  which at the beginning of this calculation, from the previous step, was originally <b>$a[$N][$M][$s-1]</b>. </p>
	<p>(2) We then multiply this entry by the entry in <i>row 1 column $N</i>, which is <b>$a[1][1][$s-1]</b>, giving <b> $a[$N][$M][$s-1] * $a[1][1][$s-1]</b>, and replace the entry in <i>row $M column 1</i> with this temporary result, <b>$tempa</b>. </p>
	<p>(3) We then multiply the entry in <i> row $M column $N</i>, <b> $a[1][$M][$s-1]</b>, by the entry in <i> row 1 column 1</i>, <b> $a[$N][1][$s-1]</b>, giving <b> $a[1][$M][$s-1] * $a[$N][1][$s-1]  = $tempb</b>.  </p>
	<p>(4) Finally, we subtract the result from the previous step, <b>$tempb</b>, from the temporary entry currently in <i>row $M column 1</i>,  <b> $tempa - $tempb </b>, and then again replace the entry in <i>row $M column 1</i> with the result, <b>$result[$s]</b>.</p>};
	foreach $t (2..$N-1) {
		$s = $N+$t-2;
		&nexta($s);
		#calculate result
		$result[$s] = ($result[$s-1] * $a[$t][$t][$s]) - ($a[$N][$t][$s] * $a[$t][$M][$s]);
		$a[$N][$M][$s] = $result[$s];
		#convert to cresult
		$cresult[$s] = &num2rods($result[$s]);
		#create formula
		$formula[$s] = "(" . $formula[$s-1];
		&pm($t);
		$formula[$s] .= qq{ ) k_{$t}  $pm };
		$formula[$s] .= qq{ l_{$N} };
		foreach my $i (1..$t -1) {
			if ($i < $t -1 ) {
				$formula[$s] .= qq{ l_{$i}  };
			}
		}
		my $u = $t-1;	# here a scalar, local variable; is a step
		$formula[$s] .= qq{ l_{$u} b_{$t} };
		$xymatrix[$s] = &xycrossmult($s);
		my $x = $t+1;
		my $y = $N-$t+1;
		my $tempa = $result[$s-1] * $a[$t][$t][$s];
		my $tempb = $a[$N][$t][$s] * $a[$t][$M][$s];
		$boardnotes[$s] .= qq{<p>We continue "cross-multiplication": </p>
	<p>(1) We again begin with the entry located in <i>row $M column 1</i>,  which at the beginning of this calculation, from the previous step, was originally <b>$result[$s-1]</b>. </p>
	<p>(2) We then multiply this entry by the entry in <i>row $t column $y</i>, which is <b>$a[$t][$t][$s]</b>, giving <b> $result[$s-1] * $a[$t][$t][$s]</b>, and replace the entry in <i>row $M column 1</i> with the temporary result <b>$tempa</b>. </p>
	<p>(3) We then multiply the entry in <i> row $M column $y</i>, <b>$a[$t][$M][$s]</b> by the entry in <i> row 1 column $t</i>, <b>$a[$N][$t][$s]</b>, giving <b>  $a[$t][$M][$s] * $a[$N][$t][$s] = $tempb</b>.  </p>
	<p>(4) Finally, we subtract the result from the previous step, <b>$tempb</b>, from the temporary entry currently in <i>row $M column 1</i>, <b> $tempa </b>, namely <b> $tempa - $tempb </b>, and then replace the temporary entry in <i>row $M column 1</i> with the result, <b>$result[$s]</b>.</p>
	<p>The resulting formula is shown below the diagram.</p>};
	};
	#Third part: calculate result
	# will probably have to be rewritten by Roger (so he says)
	# counting board is blank, he now knows how to write it
	$s++;
	$denominator = 1;
	foreach my $n (1..$N) {
		$denominator *= $a[$n][$n][0];
	}
	my $subtractand = -$a[$N][1][0];
	foreach my $n (1..$N-1) {
		$subtractand *= -$a[$n][$n+1][0];
	}
	$denominator -= $subtractand;
	&frac(1,0,$result[$s-1],$denominator);
	$result[$s] = "x_{$N} = ";
	if ($frac[2] == 0) {
		$result[$s] .= $frac[0] * $frac[1];
	}else{
		if ($frac[0] == 1) {
			$result[$s] .= "\\frac{$frac[2]}{$frac[3]}"		
		}else{
			$result[$s] .= "-\\frac{$frac[2]}{$frac[3]}"				
		}
		#$result[$N] = " \\text{ or } $mixedfrac[0]\\frac{$mixedfrac[1]}{$mixedfrac[2]}"
	}
	#convert to cresult
	#$cresult[$n] = &num2rods($result[$n]);
	#create formula
	my $denom = "";
	foreach my $n (1..$N) {
		$denom .= "k_{$n}";
	}
	$denom .= "$pm";
	foreach my $n (1..$N) {
		$denom .= "l_{$n}";
	}	
	$formula[$s]	= "x_{$N} = \\frac{" . $formula[$s-1] . "}{$denom}}";
	$boardnotes[$s] .= qq{<p>The final result: </p>};
};

sub gcf {
  my ($x, $y) = @_;
  ($x, $y) = ($y, $x % $y) while $y;
  return $x;
}

# if everything a multiple of tens, they'd reduce
sub reducetens {
	my ($n) = @_;
	if ($reducetens) {
		my $alltens = 1;
		while ($alltens) {
			foreach my $m (0..$M) {
				if (int($a[$n][$m][$s]/10) != ($a[$n][$m][$s]/10)) {
					$alltens = 0;				
				};
			}
			if ($alltens) {
				foreach my $m (1..$M) {
					$a[$n][$m][$s] = $a[$n][$m][$s] /10;
				}
			}
		}
	}
}

# part of Gaussian elimination, not determinants
sub rowReduction {
	foreach my $i (1..($N-1)) {
		if ($a[$i][$i][$s] != 0) { #need else: use another pivot
			foreach my $n (($i+1)..$N) {
				if ($a[$n][$i][$s] != 0){
					if ($a[$i][$i][$s] == $a[$n][$i][$s] ){
						foreach my $m ($i..$M) {
							$a[$n][$m][$s] = ($a[$n][$m][$s] - $a[$i][$m][$s]);
						}
						&reducetens($n);
					} else {
						my $gcf = 1; 
						if ($usegcf) { $gcf = &gcf($a[$i][$i][$s],$a[$n][$i][$s]) };
						my $nmult = $a[$i][$i][$s]/$gcf;
						my $imult = $a[$n][$i][$s]/$gcf;
						foreach my $m (1..$M) {
							$a[$n][$m][$s] = $nmult*$a[$n][$m][$s] - $imult*$a[$i][$m][$s];
						}
						&reducetens($n);						
					}
				}
			}
		}
	$a_tex[$i] = &a2tex;
	&noninteger;
	&a2c;
	$c_tex[$i] = &c2tex;
	}
}

# also part of Gaussian
sub backSubstitution {
	foreach my $i ( reverse (1..($N-1))) {
		my $bi = 0;
		$bi += $a[$N][$N][$s]*$a[$i][$M][$s];
		foreach my $j ( reverse (($i+1)..$N)) {
			$bi -= $a[$j][$M][$s]*$a[$i][$j][$s];
		}
		if ($a[$i][$i][$s] == 0 ) {
			$error .= "ann = $a[$i][$i][$s] for n = $i<p>";
		}else{
			$bi /= $a[$i][$i][$s];
			if (int($bi)!=$bi ) {
				$error .= "bi = $bi for n = $i<p>";	
			}
			$a[$i][$M][$s] = $bi;
			foreach my $k (reverse ($i..$N)) {
				$a[$i][$k][$s]=0;
			}			
		}
		&noninteger;
		$a_tex[2*$N-$i] = &a2tex;
		&a2c;
		$c_tex[2*$N-$i] = &c2tex;			
	}
}

#Fraction subroutines - Can all disappear; no fractions used

sub add {}

sub subtract {}

sub multiply {}

sub divide {}

sub reduce {}

sub frac {
	my ($sign,$int,$num,$denom) = @_;
	#put sign in $sign
	if ($int != abs($int)) {$int *= -1; $sign *= -1};
	if ($num != abs($num)) {$num *= -1; $sign *= -1};
	if ($denom != abs($denom)) {$denom *= -1; $sign *= -1};
	#calculate if fraction
	if ($num != 0){ 
		$num += $int*$denom;
		$int = 0;
		unless ($denom == 0) { #make sure not dividing by 0
			$int = int($num/$denom);
			if ( $num/$denom == $int ) { #if result is integer
				$num = 0;
				$denom = 1;
			}else{ 
				my $gcf = &gcf($num, $denom);
				$num /= $gcf;
				$denom /= $gcf;
			}	
		}
	}
	@frac = ($sign, $int, $num, $denom);
	return @frac;
}


#PRINT MATRIX SUBROUTINES
# makes them into counting rods; is for LaTeX
# not for calculations, is strictly output
# but may not be valid here anymore, moved to TeX macros
sub a2c {
	my ($s) = @_;
	unless ($noninteger) {
		foreach my $n (1..$N) {
			foreach my $m (1..$M) {
				$c[$s][$n][$m] = num2rods($a[$n][$m][$s]);
			}
		}
	}
	return @c;
}

# not being used anymore; now done through a TeX macro
sub num2rods {
	my ($number) = @_;
	# unless ($noninteger) {}
	my $rods = "";
	if ($number >= 0 ) {
		while ( $number ne "" ) { 
			my $digit = "";
			$number =~s/\d$//;
			$digit = $&;
			$rods = "~" . $rods unless ($rods eq "");
			$rods = "\\zero" . $rods if $digit == 0;
			$rods = "\\one" . $rods if $digit == 1;
			$rods = "\\two" . $rods if $digit == 2;
			$rods = "\\three" . $rods if $digit == 3;
			$rods = "\\four" . $rods if $digit == 4;
			$rods = "\\five" . $rods if $digit == 5;
			$rods = "\\six" . $rods if $digit == 6;
			$rods = "\\seven" . $rods if $digit == 7;
			$rods = "\\eight" . $rods if $digit == 8;
			$rods = "\\nine" . $rods if $digit == 9;
			if ($number ne "") {
				my $ten = "";
				$number =~s/\d$//;
				$ten = $&;
				$rods = "~" . $rods;
				$rods = "\\zero" . $rods if $ten == 0;
				$rods = "\\ten" . $rods if $ten == 1;
				$rods = "\\twenty" . $rods if $ten == 2;
				$rods = "\\thirty" . $rods if $ten == 3;
				$rods = "\\forty" . $rods if $ten == 4;
				$rods = "\\fifty" . $rods if $ten == 5;
				$rods = "\\sixty" . $rods if $ten == 6;
				$rods = "\\seventy" . $rods if $ten == 7;
				$rods = "\\eighty" . $rods if $ten == 8;
				$rods = "\\ninety" . $rods if $ten == 9;
			}
		}
	}else{
		$number = -$number;
		while ( $number ne "" ) { 
			my $digit = "";
			$number =~s/\d$//;
			$digit = $&;
			$rods = "~" . $rods unless ($rods eq "");
			$rods = "\\Zero" . $rods if $digit == 0;
			$rods = "\\One" . $rods if $digit == 1;
			$rods = "\\Two" . $rods if $digit == 2;
			$rods = "\\Three" . $rods if $digit == 3;
			$rods = "\\Four" . $rods if $digit == 4;
			$rods = "\\Five" . $rods if $digit == 5;
			$rods = "\\Six" . $rods if $digit == 6;
			$rods = "\\Seven" . $rods if $digit == 7;
			$rods = "\\Eight" . $rods if $digit == 8;
			$rods = "\\Nine" . $rods if $digit == 9;
			if ($number ne "") {
				my $ten = "";
				$number =~s/\d$//;
				$ten = $&;
				$rods = "~" . $rods;
				$rods = "\\Zero" . $rods if $ten == 0;
				$rods = "\\Ten" . $rods if $ten == 1;
				$rods = "\\Twenty" . $rods if $ten == 2;
				$rods = "\\Thirty" . $rods if $ten == 3;
				$rods = "\\Forty" . $rods if $ten == 4;
				$rods = "\\Fifty" . $rods if $ten == 5;
				$rods = "\\Sixty" . $rods if $ten == 6;
				$rods = "\\Seventy" . $rods if $ten == 7;
				$rods = "\\Eighty" . $rods if $ten == 8;
				$rods = "\\Ninety" . $rods if $ten == 9;
			}
		}
	}								
	return $rods;
}

# formulas to TeX
sub f2tex {
	 my ($s) = @_;
	$f_tex[$s] = "";
	foreach my $n (1..$N) {
		foreach my $m (1..$N) {
			if ($n == $N and $m == 1) {
				$f_tex[$s] .= qq{ l_{$N} & };
			}elsif ($n == $N and $m <= $s + 1) {
				if ($m % 2 == 0 ) {
					$f_tex[$s] .= qq{ - };
				};
				my $r = $m -1;
				$f_tex[$s] .= qq{ l_{$N} };
				foreach my $i (1..$s -1) {
					if ($i < $m -1 ) {
						$f_tex[$s] .= qq{ l_{$i}  };
					}
				}
				$f_tex[$s] .= qq{ l_{$r} & };
			}elsif ($m == $n) {
				$f_tex[$s] .= qq{ k_{$n} & };
			}elsif ($m == $n+1) {
				$f_tex[$s] .= qq{ l_{$n} & };
			}else{
				$f_tex[$s] .= qq{ 0 & };
			}; 
		};
		$f_tex[$s] .= qq{ b_{$n} \\\\  };
	};
	return $f_tex[$s];
}

# printing the tables that can take input through CGI
sub a2table {
	$print_a = qq{<table>};
	my $format = "";
	my $i = 0;		
	foreach my $n (1..$N) {
			$print_a .= qq{<tr>};
			foreach my $m (1..$N) {
			if (($m == $n+1) or ($m == $n) or ($m == 1 and $n == $N)) {
				$print_a .= qq{<td><input type="text" name="u[$n][$m]" default value="$u[$n][$m]" align="center" size="5" maxlength="5" border="0"></td>};
			}else{
				$print_a .= qq{<td>0</td>};
			}
		};
		$print_a .= qq{<td><input type="text" name="u[$n][$M]" default value="$u[$n][$M]" size="5" maxlength="5" border="0" align="center"></td>};
		$print_a .= qq{</tr>};
	};
	$print_a .= qq{</table>};
	return $print_a;
};

# outputs as augmented matrix with numbers
sub a2tex {
	my ($s) = @_;
	$matrix = "";
	foreach my $n (1..$N) {
		foreach my $m (1..$N) {
			$matrix .=qq|\\pn| unless $a[$n][$m][$s] < 0;
			$matrix .= qq{ $a[$n][$m][$s] & };
		};
		$matrix .=qq|\\pn| unless $a[$n][$M][$s] < 0;
		$matrix .= qq{ $a[$n][$M][$s] \\\\ };
	};
	return $matrix;
}

sub c2tex {
	my ($s) = @_;
	$cmatrix = "";
	unless ($noninteger){
		foreach my $m (1..$M) {
			foreach my $n (reverse (2..$N)) {
				$cmatrix .= qq{ $c[$s][$n][$m] ~ \\vline ~ & };
			};
			$cmatrix .= qq{ $c[$s][1][$m] \\\\  };
			unless ($m == $M) {$cmatrix .= qq{  \\hline   }};
		};
	};
	return $cmatrix;
};

# xymatrix subroutines
# ignore these; xy is a frustrating LaTeX macro language
# handles arrows, etc.
# needs to stay as is
# can consider improving the Perl code, but not the XY code

sub xycolwidth {
	my ($s) = @_;
	foreach my $i (1..$N) {
		my $maxwidth = 0;
		foreach my $j (1..$M) {
			my $width = ($a[$i][$j][$s] =~s/\d/$&/g);
			if ($width  > $maxwidth) {$maxwidth = $width};
		}
		my $size = 7*$maxwidth;
		$size .="mm";
		foreach my $j (1..$M) {
			$xyc[$s][$i][$j][0] = $maxwidth; 
		}
	}
	return @xyc;
}

sub addgrid {
	my ($s) = @_;
	foreach my $i (reverse (2..$N)) {
	   my $d .= "d" x ($M-1);
	   $xyc[$s][$i][1][2] .= qq|\\zud|; 
	}
	foreach my  $j (2..$M) {
		my $l .= "l" x ($N-1);
		$xyc[$s][1][$j][2] .= qq|\\zlr|;
	};
}

sub xyentries2grid {
	my ($s) = @_;
	my $xyentries2grid = "";
	&addgrid($s);
	foreach my $i (reverse (2..$N)) {
	   my $d .= "d" x ($M-1);
	   $xyentries2grid .= qq|\\zq{$a[$i][1][$s]}{$xyc[$s][$i][1][0]}{$xyc[$s][$i][1][1]}{$xyc[$s][$i][1][2]} &|; 
	}
	$xyentries2grid .= qq|\\zq{$a[1][1][$s]}{$xyc[$s][1][1][0]}{$xyc[$s][1][1][1]}{$xyc[$s][1][1][2]}\\\\|; #   \\ar\@<1ex>[$d]	
	foreach my  $j (2..$M) {
		foreach my $i (reverse (2..$N)) {
			$xyentries2grid .= qq|\\zq{$a[$i][$j][$s]}{$xyc[$s][$i][$j][0]}{$xyc[$s][$i][$j][1]}{$xyc[$s][$i][$j][2]}&|;
		}
		if ($j == 1) {
			$xyentries2grid .= qq|\\zq{$a[1][$M][$s]}{$xyc[$s][1][$M][0]}{$xyc[$s][1][$M][1]}{$xyc[$s][1][$M][2]}\\\\|;		
		}else{
			my $l .= "l" x ($N-1);
			$xyentries2grid .= qq|\\zq{$a[1][$j][$s]}{$xyc[$s][1][$j][0]}{$xyc[$s][1][$j][1]}{$xyc[$s][1][$j][2]}\\\\|;
		}
	};
	return $xyentries2grid;
}

sub xysetneg { #NOTE: AVOID % in expressions for mathtex -- I don't know if lines are separated! 
	my ($s) = @_;
	unless ($noninteger){
		#First make all the entries in each column the same width
		#Second add boxes and arrows where appropriate
		if ($s==0) {
			&xycolwidth($s);
			foreach my $i (reverse (1..$N)) {
				foreach my  $j (1..$M) {
					$xyc[$s][$i][$j][1] = qq|m|;
					$xyc[$s][$i][$j][2] = qq||;
				}
			}
		}elsif ($s > 0) {
			#make boxes
			foreach my $i (reverse (1..$N)) {
				foreach my  $j (1..$M) {
					#$xyc[$s][$i][$j][2] .= qq| ($i,$j) |;
					#$xyc[$s][$i][$j][1] = qq|f|;
					if ( $j == ($s+1) and $i == $s) {
						$xyc[$s][$i][$j][1] = qq|f|; #   \\ar\@<1ex>[$d]				
					}elsif ( $j == $s and $i == $N ) {
						$xyc[$s][$i][$j][1] = qq|f|;				#  
					}elsif ( $j == ($s+1) and $i == $N ) {
						$xyc[$s][$i][$j][1] = qq|f|;				# *+<2mm,2mm>[F-:<4pt>] 
					}else{
						$xyc[$s][$i][$j][1] = qq|m|;		#to keep sizes the same
					}
				}
			}
			#make columns equal
			&xycolwidth($s);
			#add arrows
			foreach my $i (reverse (1..$N)) {
				foreach my  $j (1..$M) {
					#$xyc[$s][$i][$j][2] .= qq| ($i,$j) |;
					if ( $j == ($s+1) and $i == ($s)) {
						my $u .= "u";
						my $d .= "d" x $M;
						my $l .= "l" x ($N-$s);
						$xyc[$s][$i][$j][2] = qq|\\POS[]+U\\ar\@/_5mm/[$u$l]|; #   \\ar\@<1ex>[$d]				
					}elsif ( $j == $s and $i == $N ) {
						$xyc[$s][$i][$j][2] = qq|\\POS[]+R\\ar\@/^5mm/[d]+R|;				#  
					}
				}
			}
		}
		#Finally, place entries and add grid
		$xymatrix[$s] = &xyentries2grid($s);
	};
	return $xymatrix[$s];
}

sub xycrossmult { #NOTE: First place entries, then place arrows 
	my ($s) = @_;
	my $t = $s - $N + 2;
	unless ($noninteger){
		#Set the answer in aNM
		$c[$s] = $c[$N-2];
		$c[$s][$N][$M] = $cresult[$s];
		#First add boxes where appropriate
		foreach my $i (reverse (1..$N)) {
			foreach my  $j (1..$M) {
				if ($i ==$N  and $j == $M) { #add save/restores?
					$xyc[$s][$i][$j][1] = qq|f|;										
				}elsif ($i ==$t  and $j == $t) {
					my $d .= "d" x ($N-$t+1);
					my $l .= "l" x ($N-$t);
					$xyc[$s][$i][$j][1] = qq|f|;										
				}elsif ( $i == $t and $j ==$M ) {
					my $d .= "d" x ($N-$t+1);
					my $l .= "l" x ($N-$t);
					$xyc[$s][$i][$j][1] .= qq|f|;										
				}elsif ( $i == $N and $j == $t ) {
					my $d .= "d" x ($N-$t+1);
					my $r .= "r" x ($N-$t);
					$xyc[$s][$i][$j][1] .= qq|f|;										
				}else{
					$xyc[$s][$i][$j][1] = qq|m|;		#to keep sizes the same
					#$xyc[$s][$i][$j][2] = qq| { \\tiny{($i,$j)} $c[$N-2][$i][$j]} |;					
				}
			}
		}			
		#Second make columns equal
		&xycolwidth($s);
		#Third add arrows where appropriate
		my $curve;
		my $offset;
		my $r = $N-2;
		foreach my $i (reverse (1..$N)) {
			foreach my  $j (1..$M) {
				if ($i ==$t  and $j == $t) {
					my $d .= "d" x ($N-$t+1);
					my $l .= "l" x ($N-$t);
					if ( $t <=  $N-2 ) {$curve = "8mm";	 $offset ="+UR"}else{$curve = "2mm"; $offset ="+UR+<-2mm,0mm>"};
					$xyc[$s][$i][$j][2] .= qq|\\POS[]+L+<2mm,0mm>\\ar\@/_$curve/[$l$d]$offset|;										
				}elsif ( $i == $t and $j ==$M ) {
					my $d .= "d" x ($N-$t+1);
					my $l .= "l" x ($N-$t);
					if ( $t <=  $N-2 ) {$curve = "8mm";	 $offset =""}else{$curve = "2mm"; $offset =""};
					$xyc[$s][$i][$j][2] .= qq|\\POS[]+L+<1mm,0mm>\\ar\@/^$curve/[$l]+R|;										
				}elsif ( $i == $N and $j == $t ) {
					my $d .= "d" x ($N-$t+1);
					my $r .= "r" x ($N-$t);
					if ( $t <=  $N-2 ) {$curve = "4mm";	 $offset ="+UL"}else{$curve = "1mm"; $offset ="+U"};
					$xyc[$s][$i][$j][2] .= qq|\\POS[]+R\\ar\@/^$curve/[$d$r]$offset|;										
				}
			}
		}
	
		#$xyc[$s][$N][1][2] .= qq| t=$t; |;
		#Finally, place entries and add grid
		#$c[$s][1][1] = qq| {\\setlength\\fboxrule{0pt}\\fbox{New $s Old cell $c[$N-2][1][1]}} |;
		$xymatrix[$s] = &xyentries2grid($s); 
	};
	return $xymatrix[$s];
}

sub final { #NOTE: AVOID % in expressions for mathtex -- I don't know if lines are separated! 
	my ($s) = @_;
	my $t = $s - $N + 2;
	unless ($noninteger){
		#Set the answer in aNM
		$c[$s] = $c[$N-2];
		$c[$s][$N][$M] = $cresult[$s];
		#First make all the entries in each column the same width
		&xycolwidth($s);
		#Second add boxes and arrows where appropriate
		my $curve = "1mm";
		my $r = $N-2;
		if ( $t <=  $N-2 ) {
			$curve = "5mm";
		}
		foreach my $i (reverse (1..$N)) {
			foreach my  $j (1..$M) {
				if ($i ==$N  and $j == $M) {
					$xyc[$s][$i][$j][2] .= qq| \\fbox{$c[$s][$i][$j] } |;										
				}elsif ($i ==$t  and $j == $t) {
					my $d .= "d" x ($N-$t+1);
					my $l .= "l" x ($N-$t);
					$xyc[$s][$i][$j][2] .= qq| \\fbox{$c[$s][$i][$j] }\\POS[]+DL+<1mm,1mm> \\ar\@/_$curve/[$l$d]+UR+<-1mm,-1mm> |;										
				}elsif ( $i == $t and $j ==$M ) {
					my $d .= "d" x ($N-$t+1);
					my $l .= "l" x ($N-$t);
					$xyc[$s][$i][$j][2] .= qq| \\fbox{$c[$s][$i][$j]} \\POS[]+DL+<1mm,1mm> \\ar\@/^$curve/[$l]+DR+<-1mm,1mm>  |;										
				}elsif ( $i == $N and $j == $t ) {
					my $d .= "d" x ($N-$t+1);
					my $r .= "r" x ($N-$t);
					$xyc[$s][$i][$j][2] .= qq| \\fbox{$c[$s][$i][$j]}\\POS[]+DR+<-1mm,1mm> \\ar\@/^$curve/[$d$r]+UL+<1mm,-1mm> |;										
				}else{
					$xyc[$s][$i][$j][2] = qq| {\\setlength\\fboxrule{0pt}\\fbox{$c[$s][$i][$j]}} |;					
					#$xyc[$s][$i][$j][2] = qq| { \\tiny{($i,$j)} $c[$N-2][$i][$j]} |;					
				}
			}
		}
	
		#$xyc[$s][$N][1][2] .= qq| t=$t; |;
		#Finally, place entries and add grid
		#$c[$s][1][1] = qq| {\\setlength\\fboxrule{0pt}\\fbox{New $s Old cell $c[$N-2][1][1]}} |;
		$xymatrix[$s] = &xyentries2grid($s); 
	};
	return $xymatrix[$s];
}



#PRINT HTML SUBROUTINES
# here's where he wants the most help
# improve the HTML

sub print_header {	# style = "font-size: 12px; font-family: 'Impact'; background-color : yellow;  font-weight : bold;  font-size: 12px; font-family: 'Helvetica'; text-decoration : underline"
	my $print_header = qq{ 
		<style type="text/css">
		p {font-family: serif; font-weight: lighter;}
		h3 {font-family: Arial Arial Black; font-weight: bolder; }
		th {font-family: Arial Arial Black; font-size: small; text-align: center; vertical-align: bottom; border-collapse: collapse; border-spacing: 0px 0px;}
		td {font-family: Arial Arial Black; text-align: center; vertical-align: center; border-collapse: collapse; border-spacing: 0px 0px; width: 5em}
		table {border-collapse: separate; border-spacing: 0px 1px; border: 1px solid black; table-layout: fixed; font-color: blue; } 
		</style> }; 	# background-color: #bbf
	# 	$print_header .= qq{<tr><th colspan = "1"></th>};
	# 	foreach my $m (@m) {
	# 		$print_header .= qq{<th colspan = "1">$m</th>};
	# 	};
	#	$print_header .= qq{</tr>};
};

#PRINT LATEX OUTPUT
# 	{\setlength{\arrayrulewidth}{0.05pt} %default is 0.4pt
#   \setlength{\arraycolsep}{2pt}%default is 5pt
#  \renewcommand{\arraystretch}{1.2}%default is 1

sub createout1 {
	my $L=$N-1;
	foreach my $s (0..$N-2) {
		$output[$s] .= qq|
			<p></p>
			<h4>Step $s</h4>
			<p>$boardnotes[$s]</p>
			<p>
		    <img src="../cgi-bin/mathtex.cgi?
		    \\dpi{100}
		    \\def\\zN{$N}
		    \\def\\zL{$L}
		    \\fbox{\\xymatrix \@H= 5mm {$xymatrix[$s]}}
			" alt="" border=0 align=middle>
			</p>
			<p>$calcnotes[$s]</p>
			<p><img src="../cgi-bin/mathtex.cgi?
			\\usepackage{euler}
			\\begin{equation*}
			\\begin{bmatrix}
				$a_tex[$s]
			\\end{bmatrix}
			\\end{equation*}
			" alt="" border=0 align=middle>
			<p>
			$formulanotes[$s] 
			<img src="../cgi-bin/mathtex.cgi?
			\\usepackage{euler}
			\\begin{equation*}
			\\begin{bmatrix}
			$f_tex[$s]
			\\end{bmatrix}
			\\end{equation*}
			" alt="" border=0 align=middle></p>
		|;
	};
	return @output;
}

sub createout2 {
	my $L=$N-1;
	foreach my $s ($N-1..2*$N-2){
		$output[$s] .= qq|
			<p>
			<h4>Step $s</h4>
			<p>
			<p>$boardnotes[$s]</p>
			<p>
		    <img src="../cgi-bin/mathtex.cgi?
		    \\dpi{100}
		    \\def\\zN{$N}
		    \\def\\zL{$L}
		    \\fbox{\\xymatrix \@H= 5mm {$xymatrix[$s]}}
			" alt="" border=0 align=middle>
			</p><p>
			<img src="../cgi-bin/mathtex.cgi?
			\\usepackage{euler}
			\\begin{equation*}
				$result[$s] 
			\\end{equation*}
			" alt="" border=0 align=middle>
			<p>
			<img src="../cgi-bin/mathtex.cgi?
			\\usepackage{euler}
			\\begin{equation*}
				$formula[$s]
			\\end{equation*}
			" alt="" border=0 align=middle>
		|;
	}
	return @output;
}

sub createout3 {
	my $laststep = 2*$N-1;
	$output[$laststep] .= qq{
		<p>
		<h4>Step $laststep</h4>
		<p>
		$boardnotes[$s]
		<img src="../cgi-bin/mathtex.cgi?
		\\usepackage{euler}
		\\begin{equation*}
			$result[$laststep]
		\\end{equation*}
		" alt="" border=0 align=middle>
		 <p>
		<img src="../cgi-bin/mathtex.cgi?
		\\usepackage{euler}
		\\begin{equation*}
			$formula[$laststep]
		\\end{equation*}
		" alt="" border=0 align=middle>
		<p>
	};
	return @output;
}


#CGI SUBROUTINES
my $which_one = param('button_name');
my $stepmessage; 
my $stepoutput = "";
my $nextstep;
sub choose_options {	
	if ($which_one == "Next step" ) {
		$step = $query->param('step'); 
		$nextstep = $step;
		$nextstep++;
		$stepmessage = "<p>My new step is $step</p>";
	}else{
		$step=0;
		$nextstep = $step;	
		$nextstep++;
	}
	if ($query->param("u[1][1]")) {
		$m_num = $query->param('old_m_num'); #= $query->param("N");
		$N = $query->param('N'); #= $query->param("N");
		$error .= " <p>My old N is $N </p>";
		$M = $N+1;
		foreach my $n (1..$N) {
			foreach my $m (1..$M) {
				if (($m == $n+1) or ($m == $n) or ($m == 1 and $n == $N) or $m == $M) {
					my $input = $query->param("u[$n][$m]");
					$input =~ s/\s+//g;
					if ($input =~ m/^\-?\d+(\/\d+)?$/) {
 						$u[$n][$m] = $input;
  					}else{
 						$inputerror .= qq{<p>"$input" is not valid input. Entries must be an integer or a proper fraction. };
  						if ($input =~ m/\-?\d+(\/\d+)?/) {
  	 						$u[$n][$m] = $&;					
  						}else{
  				 			$u[$n][$m] = 0;
 						}						
 						$inputerror .= qq{The entry has been set to $u[$n][$m].</p>};
 					}
				}else{
					$u[$n][$m] = 0;
				}
				$m[$m_num][$n-1][$m-1] = "$u[$n][$m]";
			}
		}
		&m2a($m_num);
	}elsif ($query->param('m_num') && ($query->param('m_num') != $m_num)) {
		$m_num = $query->param('m_num');
		&m2a($m_num);
	}elsif (0==1){ # ($query->param('N') && ($query->param('N') != $N)) {
		$N = $query->param('N');
		unless (($N >= 1) and ($N <= 5)) {$N = 3};
		$M = $N + 1;
		&random2a;
	}
	if ($query->param('usegcf')) {
		$usegcf = $query->param('usegcf');
		unless ($usegcf == 1) {$usegcf = 0};
	}
}

#PRINT HTML PAGE

print $query->header, 
	$query->start_html('Chinese linear algebra'), 
	h2('Determinants'),
	p,
	start_form,
	hr,
	"Problem:",  popup_menu(-name=>'m_num', -values=>\@JZSSproblems, -default=>""),
	p,
	submit(-name=>'Choose new problem'),
	p,
	$error,
	end_form;
$query->end_html; 
my @steps;
#PROCESS SUBROUTINES
if (defined($query->param('m_num'))) {
	&choose_options;
	$table_a = &a2table; 
	$table_header = &print_header; 
	#&rowReduction;
	#&backSubstitution;
	#&divideANN;
	&determinants;
	&createout1;
	&createout2;
	&createout3;
	@steps = (0..2*$N-2);
	print 
		start_form,
		hr,
		hidden(-name=>'N', -default=>["$N"]),
		hidden(-name=>'old_m_num', -default=>["$m_num"]),
		p, $table_header, $table_a, p,
		submit(-name=>'Recalculate with new values'), p,
		"$inputerror",
		p,		
		# reset(-name=>'Reset to original values'), p,
		hr,
		qq{<p>$output[$step]</p>},
		p,
		submit(-name=>'Next step', -value=>'Go to step'),
		popup_menu (-name=>'step', -values=>\@steps, -default=>"$nextstep", -override=>1),
		#qq{$newstep},
		hr;
# 		foreach my $i (1..3*$N) {
# 			print qq{<p>Output $i</p>$output[$i]};
# 		}
		# print qq{$stepoutput};
		end_form;
	$query->end_html; 
	#$query->delete_all();
}

# 
# 	my @names = $query->param;
# 	$error .="@names ";
# 	
# 	my $params = $query->Vars;
# 	print $params->{'address'};
# 	my @foo = split("\0",$params->{'foo'});
# 	my %params = $query->Vars;
# 	use CGI ':cgi-lib';
# 	$params = Vars;
# 	$error .="$params";
# 	foreach my $key (%params) {
# 		$error .= "<p>$key => $params{$key}</p>";
# 	}
# 	print qq{$error};


